/* ************************************************************************
 * Program: qsort.c
 * Description: Matrix multiplication using llc compiler.
 * Date: 27.04.2001
 * Last Rev.: 1.5.2001 F. de Sande
 * F. de Sande
 **************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "mytime.h"

#define KILO (1024)
#define MEGA (1024 * 1024)
#define MAXSIZE  (9 * MEGA)
#define MAX_REP 10             /* No. of iterations (number of vectors to sort) */

char usage_str[] = "<size_in_Kb>";
double SEQ[MAX_REP];                                        /* Sequential time */
double PAR[MAX_REP];                                        /* Parallel time */
double SPEED[MAX_REP];                                      /* Speedup */
double par_m, seq_m, spe_m;                                 /* Averages */
int SIZE;
int array[MAXSIZE];      

void press_key(void);
void write_array(int *v);
void initialize(int *v, int seed);
void testit(int *v);
void find(int *v, int first, int last, int middle);
void quicksortseq(int *v, int first, int last);
void qs(int *v, int first, int last);

/****************************************************************************/
/* Sets randomly the values for the array */
void initialize(int *v, int seed) {
  unsigned i;

  /* LLC_printMaster("Seed: %d size: %d\n", seed, SIZE); */
  srandom(seed);
  for(i = 0; i < SIZE; i++)
    v[i] = (int)random();
}
/****************************************************************************/
/* Escribe el array */
void write_array(int *v) {
  unsigned i;

  for(i = 0; i < SIZE; i++)
    LLC_printMaster("LLC_NAME: %d v[%u] = %i\n", LLC_NAME, i, v[i]);
}
/****************************************************************************/
void testit(int *v) {
  int k, not_sorted = 0;

  for (k = 0; k < SIZE - 1; k++)
    if (v[k] > v[k + 1]) {
      not_sorted = 1;
      break;
    }

  if (not_sorted) {
    printf("Processor %d: NOT sorted.\n", LLC_NAME);
  }
  /*
  else {
    LLC_printMaster("%d#: Array sorted. Size: %d first: %d last: %d\n", LLC_NAME, SIZE, v[0], v[SIZE-1]);
  }
  */
}
/****************************************************************************/
/* Quicksortcclasico (Wirth) */
void quicksortseq(int *v, int first, int last) {
  register int i, j, pivot, temp;

  i = first;
  j = last;
  pivot = v[(first + last) / 2];
  do {
    while (v[i] < pivot)
      i++;
    while (pivot < v[j])
      j--;
    if (i <= j) {
      temp = v[i];    /* swap v[i] and v[j] */
      v[i] = v[j];
      v[j] = temp;
      i++;
      j--;
    }
  } while (i <= j);
  if (first < j)
    quicksortseq(v, first, j);
  if (i < last)
    quicksortseq(v, i, last);
}
/****************************************************************************/
int main(int argc, char *argv[]) {
  int first, last;                      /* Range to sort in the array */
  int REP, seed, j;
  double t_seq, t_par;
  CLOCK_TYPE chrono;

  if (argc == 2) {
    SIZE = atoi(argv[1]) * (KILO);
    if (SIZE > MAXSIZE) {
      LLC_printMaster("Size: %d Maximum size: %d\n", SIZE, MAXSIZE);
      exit(-1);
    }
  }
  else {
    LLC_printMaster("\nUse: %s usage_str\n", argv[0], usage_str);
    exit(-1);
  }
  for (REP = 0; REP < MAX_REP; REP++) {
/*    LLC_printMaster("Rep: %d\n", REP); */
    seed = (REP + 1) * 7;
    initialize(array, seed);
    /*** SEQ *********************************************************/
    CLOCK_Start(chrono);
    quicksortseq(array, 0, SIZE-1);
    CLOCK_End(chrono, t_seq);
    SEQ[REP] = t_seq;
    testit(array);
      
    initialize(array, seed);
    /** PAR **********************************************************/
    CLOCK_Start(chrono);
    qs(array, 0, SIZE-1);
    CLOCK_End(chrono, t_par);
    PAR[REP] = t_par;
    testit(array);
  }
  par_m = seq_m = spe_m = 0.0;
  for (REP = 0; REP < MAX_REP; REP++) {
    par_m += PAR[REP];
    seq_m += SEQ[REP];
    spe_m += SEQ[REP] / PAR[REP];
  } 
  par_m = par_m / (1.0 * MAX_REP);
  seq_m = seq_m / (1.0 * MAX_REP);
  spe_m = spe_m / (1.0 * MAX_REP);


  LLC_printMaster("\n\n*************************************************************************\n");
  LLC_printMaster("\tNP = %d. NAME = %d. SIZE = %d. REP = %d.\n", 
  							LLC_NUMPROCESSORS, LLC_NAME, SIZE, REP);
  LLC_printMaster("\tTIME (AVERAGE):  SEQ = %g, PAR = %g. SPEEDUP (AVERAGE) = %g\n",
							seq_m, par_m, spe_m);
  LLC_printMaster ("%d\t%g\t#llc_plot QSORT_FORALL:SIZE=%d REP=%d (t_seq_m=%g/t_par_m=%g)\n", 
                    		LLC_NUMPROCESSORS, spe_m, SIZE, REP, seq_m, par_m);
  LLC_printMaster("******************************************************************************\n\n");
} /* main */

/************************************************************/
void qs(int *v, int first, int last) {
  int size[2], start[2], end[2], *res[2], pivot, i, temp;

  if (first < last) {
    start[1] = first;
    end[0] = last;
    pivot = v[(first + last) / 2];
    while (start[1] <= end[0]) {
      while (v[start[1]] < pivot)
        start[1]++;
      while (pivot < v[end[0]])
        end[0]--;
      if (start[1] <= end[0]) {
        temp = v[start[1]];
        v[start[1]] = v[end[0]];
        v[end[0]] = temp;
        start[1]++;
        end[0]--;
      }
    }

    size[0]  = (end[0] - first + 1);
    start[0] = first; 
    res[0]   = v + first; 
     
    size[1]  = (last - start[1] + 1);
    end[1]   = last; 
    res[1]   = v + start[1]; 

    #pragma omp target device (mpi)
    #pragma omp parallel for	 
    //TODO #pragma llc weight(size[i])
    //TODO#pragma llc result(res[i], size[i])
    for(i = 0; i <= 1; i++) {
      qs(v, start[i], end[i]);
    }
	 
  }
}
